#!/usr/bin/python
#
#    Copyright 2006 Andrew Wilkinson <aw@cs.york.ac.uk>.
#
#    This file is part of PyScobble (http://lastfm.indiegigs.co.uk/pyscrobble)
#
#    PyScobble is free software; you can redistribute it and/or modify
#    it under the terms of the GNU Lesser General Public License as published by
#    the Free Software Foundation; either version 2.1 of the License, or
#    (at your option) any later version.
#
#    PyScobble is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#    GNU Lesser General Public License for more details.
#
#    You should have received a copy of the GNU Lesser General Public License
#    along with PyScobble; if not, write to the Free Software
#    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
#

import sys

import scrobble
from lastfm6degrees import chaintypes

def findChain(user1, user2, forward, reverse, reverse_conclusive, mutual, notify):
    found = {user1: []}
    todo = [([], [user1, ])]
    count = 1
    rfound = {user2: []}
    rtodo = [([], [user2, ])]
    rcount = 1

    notify("depth", 0)
    depth = 0
    notify("checked", 0)
    checked = 0
    notify("remaining", 0)
    remaining = 0

    while count > 0 and (rcount > 0 or not reverse_conclusive):
        if ((reverse_conclusive and count <= rcount) or (count <= rcount*5)) or rcount == 0:
            (prev, users), todo = todo[0], todo[1:]
            count -= len(users)
            notify("depth", len(prev))
            for user in users:
                if mutual:
                    friends = [f for f in forward(user) if f not in found and mutual(user, f)]
                else:
                    friends = [f for f in forward(user) if f not in found]
                checked += 1
                remaining -= 1
                notify("checked", checked)
                notify("remaining", remaining)
                for f in friends:
                    if f in rfound:
                        yield prev + [user, f] + rfound[f]
                    found[f] = prev + [user]
                remaining += len(friends)
                notify("remaining", remaining)
                todo.append((prev + [user], friends))
                count += len(friends)
                yield None
        else:
            (prev, users), rtodo = rtodo[0], rtodo[1:]
            rcount -= len(users)
            notify("depth", len(prev))
            for user in users:
                if mutual:
                    friends = [f for f in reverse(user) if f not in rfound and mutual(f, user)]
                else:
                    friends = [f for f in reverse(user) if f not in rfound]
                checked += 1
                remaining -= 1
                notify("checked", checked)
                notify("remaining", remaining)
                for f in friends:
                    if f in found:
                        yield found[f] + [f, user] + prev
                    rfound[f] = [user] + prev
                remaining += len(friends)
                notify("remaining", remaining)
                rtodo.append(([user] + prev, friends))
                rcount += len(friends)
                yield None
    yield False

def notify(text, value):
    print text, value

def main():
    user1 = scrobble.User(sys.argv[1])
    user2 = scrobble.User(sys.argv[2])
    chain = findChain(user1, user2, chaintypes.getUserFriends, chaintypes.getUserReverseFriends, None, notify)

    print " -> ".join([str(u) for u in chain])

if __name__ == "__main__":
    if len(sys.argv) == 3:
        main()
    else:
        from lastfm6degrees import gui
        gui.runGUI(findChain, chaintypes)
